package SubjectTree.One;

import java.util.ArrayList;
import java.util.Collections;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

import Utility.TreeNode;

public class LevelOrderBottom {

/**
 * 难度：简单
 * 
 * 107. 二叉树的层序遍历 II
 * 	给定一个二叉树，返回其节点值自底向上的层序遍历。 （即按从叶子节点所在层到根节点所在的层，逐层从左向右遍历）
 * 
 * 例如：
 * 	给定二叉树 [3,9,20,null,null,15,7],
 * 	    3
 * 	   / \
 * 	  9  20
 * 	    /  \
 * 	   15   7
 * 	返回其自底向上的层序遍历为：
 * 	
 * 	[
 * 	  [15,7],
 * 	  [9,20],
 * 	  [3]
 * 	]
 *
 * */
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		LevelOrderBottom lob = new LevelOrderBottom();
		TreeNode root = TreeNode.MkTree("[3,9,20,null,null,15,7]");
		System.out.println(lob.levelOrderBottom(root));
	}
	//方法一：广度优先搜索
	public List<List<Integer>> levelOrderBottom(TreeNode root) {
		List<List<Integer>> ret = new ArrayList<>();
		if(root==null)return ret;
		Queue<TreeNode> queue = new LinkedList<>();
		queue.offer(root);
		while(!queue.isEmpty()) {
			List<Integer> list = new ArrayList<>();
			int currentLevelSize = queue.size();
			for(int i=0;i<currentLevelSize;i++) {
				TreeNode node = queue.poll();
				list.add(node.val);
				if(node.left!=null)queue.offer(node.left);
				if(node.right!=null)queue.offer(node.right);
			}
			ret.add(list);
		}
		Collections.reverse(ret);
		return ret;
    }
}
